package com.stephen.data.sort;

import java.util.Arrays;

/**
 * @author: stephen
 * @create: 2020-01-31 17:26
 * @description: 插入排序,比选择排序更快
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arr = {1,-1,2,100,99};
        System.out.println(Arrays.toString(sort(arr)));

        // 测试排序时间
        int[] arrTest = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arrTest[i] = (int)(Math.random() * 8000000);
        }
        long start = System.currentTimeMillis();
        sort(arrTest);
        long end = System.currentTimeMillis();
        System.out.printf("排序时长: [%d]毫秒",end - start); //[1034]毫秒

    }

    public static int[] sort(int[] arr) {
        // 下标为0的数先固定
        // 从下标1开始,找位置,除了第0个数,其他数都需要找位置
        // 共 arr.length-1 次循环
        for (int i = 1; i < arr.length; i++) {
            // 定义待插入的数
            int insertval = arr[i];
            // 初始插入位置为i-1
            int insertIndex = i - 1;

            // 如果满足条件,说明该数较小,
            while (insertIndex >= 0 && insertval < arr[insertIndex]) {
                // 移动其左边的数,向右移一位
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            // 循环结束,已找到合适位置,把值放过去即可
            // 若元素没有移动,则不需要赋值
            if (insertIndex != i - 1) {
                arr[insertIndex + 1] = insertval;
            }
        }
        return arr;
    }

}
